//https://leetcode.cn/problems/minimum-window-substring/description/
class Solution {
    public String minWindow(String s, String t) {
        int left = 0;
        int right = 0;
        int minL = s.length() + 1;
        String str = null;
        int[] hash1 = new int[52 + 6];
        int[] hash2 = new int[52 + 6];
        for (int i = 0; i < t.length(); i++) {
            hash1[t.charAt(i) - 'A']++;
        }
        while (right < s.length()) {
            hash2[s.charAt(right) - 'A']++;

            while (check(hash1, hash2)) {
                if (right - left + 1 < minL) {
                    minL = right - left + 1;
                    str = s.substring(left, right + 1);
                }
                hash2[s.charAt(left) - 'A']--;
                left++;
            }
            right++;
        }
       return minL == s.length()+1 ? "" : str;
    }

    private boolean check(int[] hash1, int[] hash2) {
        for (int i = 0; i < hash1.length; i++) {
            if (hash1[i] > hash2[i]) {
                return false;
            }
        }
        return true;
    }
}